//测试-平衡二叉搜索树
//编译：g++ TestAVLTree.cpp ../../*/*/AVLTree.hpp -o test
#ifndef __TESTAVLTREE__CPP
#define __TESTAVLTREE__CPP

#include<iostream>
#include"../../DataStructure/Tree/AVLTree.hpp"

using namespace std;
using namespace NgSiuKei;

int main(void) {
    //先造个二插搜索树
    binary_tree_node<int> *tree12 = createTree(12, (binary_tree_node<int> *)nullptr, (binary_tree_node<int> *)nullptr);
    binary_tree_node<int> *tree25 = createTree(25, (binary_tree_node<int> *)nullptr, (binary_tree_node<int> *)nullptr);
    binary_tree_node<int> *tree30 = createTree(30, (binary_tree_node<int> *)nullptr, (binary_tree_node<int> *)nullptr);
    binary_tree_node<int> *tree37 = createTree(37, (binary_tree_node<int> *)nullptr, (binary_tree_node<int> *)nullptr);
    binary_tree_node<int> *tree50 = createTree(50, (binary_tree_node<int> *)nullptr, (binary_tree_node<int> *)nullptr);
    binary_tree_node<int> *tree75 = createTree(75, (binary_tree_node<int> *)nullptr, (binary_tree_node<int> *)nullptr);

    insertLeftSubTree(tree50, tree25);
    insertRightSubTree(tree50, tree75);
    insertLeftSubTree(tree25, tree12);
    insertRightSubTree(tree25, tree37);
    insertLeftSubTree(tree37, tree30);

    if(!isBST(tree50)) {
        cout << "不是二叉搜索树，请重试设置树" << endl;
        return 0;
    }
    if(isAVLTree(tree50)) {
        cout << "已经是AVL树了，请重新设置树" << endl;
        return 0;
    }

    U_L_L num = getTreeNodeNum(tree50);

    cout << "tree50 = " << tree50 << endl;
    cout << "tree50.val = " << tree50->val << endl;
    cout << "num = " << getTreeNodeNum(tree50) << endl;
    cout << "height = " << getTreeHeight(tree50) << endl;

    int *preArray = orderTree(tree50, ORDER_TYPE_PRE);
    int *inArray = orderTree(tree50, ORDER_TYPE_IN);
    int *postArray = orderTree(tree50, ORDER_TYPE_POST);
    int *levelArray = orderTree(tree50, ORDER_TYPE_LEVEL);

    cout << "前序 = [ ";
    for(U_L_L i=0; i<num; ++i) {
        cout << preArray[i] << ' ';
    }
    cout << ']' << endl;

    cout << "中序 = [ ";
    for(U_L_L i=0; i<num; ++i) {
        cout << inArray[i] << ' ';
    }
    cout << ']' << endl;

    cout << "后序 = [ ";
    for(U_L_L i=0; i<num; ++i) {
        cout << postArray[i] << ' ';
    }
    cout << ']' << endl;

    cout << "层序 = [ ";
    for(U_L_L i=0; i<num; ++i) {
        cout << levelArray[i] << ' ';
    }
    cout << ']' << endl;

    cout << "=======BST->AVL============" << endl;
    convertToAVLTree(tree50);

    cout << "tree50 = " << tree50 << endl;
    cout << "tree50.val = " << tree50->val << endl;
    cout << "num = " << getTreeNodeNum(tree50) << endl;
    cout << "height = " << getTreeHeight(tree50) << endl;

    preArray = orderTree(tree50, ORDER_TYPE_PRE);
    inArray = orderTree(tree50, ORDER_TYPE_IN);
    postArray = orderTree(tree50, ORDER_TYPE_POST);
    levelArray = orderTree(tree50, ORDER_TYPE_LEVEL);

    cout << "前序 = [ ";
    for(U_L_L i=0; i<num; ++i) {
        cout << preArray[i] << ' ';
    }
    cout << ']' << endl;

    cout << "中序 = [ ";
    for(U_L_L i=0; i<num; ++i) {
        cout << inArray[i] << ' ';
    }
    cout << ']' << endl;

    cout << "后序 = [ ";
    for(U_L_L i=0; i<num; ++i) {
        cout << postArray[i] << ' ';
    }
    cout << ']' << endl;

    cout << "层序 = [ ";
    for(U_L_L i=0; i<num; ++i) {
        cout << levelArray[i] << ' ';
    }
    cout << ']' << endl;

    if(isAVLTree(tree50)) {
        cout << "转换成功" << endl;
    }

    clearTree(tree50);
    delete preArray;
    delete inArray;
    delete postArray;
    delete levelArray;

    return 0;
}

#endif